package leetcode_121_140;

import java.util.*;

public class minCut_132 {
    /**
     * 类似上一题，但是要求返回最短切割次数
     * 利用贪心算法
     * 还是超时了
     */
    public int minCut(String s) {
        char[]chars=s.toCharArray();
        HashMap<Integer, TreeSet<Integer>> map=new HashMap<>();
        //记录每个坐标以及以该坐标为起始字母的所有回文串的结尾坐标
        for(int i=0;i<chars.length;i++){
            TreeSet<Integer> end = new TreeSet<>(((o1,o2)->o2.compareTo(o1)));  //设置为降序
            //自身也算回文串
            end.add(i);
            map.put(i,end);
            int l=i-1,r=i+1;
            //中心扩散
            //奇数长度的回文串
            while(l>-1 && r<chars.length){
                if(chars[l]==chars[r]){
                    map.get(l).add(r);
                    l--;
                    r++;
                } else
                    break;
            }
            //偶数长度的回文串
            if (i!=chars.length-1 && chars[i] == chars[i + 1]) {
                map.get(i).add(i+1);
                l=i-1;r=i+2;
                while (l > -1 && r < chars.length) {
                    if (chars[l] == chars[r]) {
                        map.get(l).add(r);
                        l--;
                        r++;
                    } else
                        break;
                }
            }
        }

        function(chars,0,map,0);
        return minCut;
    }

    int minCut=Integer.MAX_VALUE;
    /**
     * 递归组合回文串所有可能性
     * 采用贪心算法，每次都先使用最长的回文串
     * 返回值为回文串最小数量
     */
    int function(char[] chars,int index,HashMap<Integer,TreeSet<Integer>>map,int count){
        if(minCut< count)
            return 0;

        if(index==chars.length){
            minCut=Math.min(minCut,count-1);
            return count;
        }


        //因为是降序的set集合，可以直接使用贪心
        for(int i:map.get(index)){
            function(chars,i+1,map,count+1);
        }

        return count;
    }


    /**
     * 高解动态规划
     * 思路有一点点类似我用的map思路，但是数组明显更容易操作和理解
     * @param s
     * @return
     */
    public int minCut2(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        // g[l][r] 代表 [l,r] 这一段是否为回文串
        boolean[][] g = new boolean[n + 1][n + 1];
        for (int r = 1; r <= n; r++) {
            for (int l = r; l >= 1; l--) {
                // 如果只有一个字符，则[l,r]属于回文
                if (l == r) {
                    g[l][r] = true;
                } else {
                    // 在 l 和 r 字符相同的前提下
                    if (cs[l - 1] == cs[r - 1]) {
                        // 如果 l 和 r 长度只有 2；或者 [l+1,r-1] 这一段满足回文，则[l,r]属于回文
                        if (r - l == 1 || g[l + 1][r - 1]) {
                            g[l][r] = true;
                        }
                    }
                }
            }
        }

        // f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数
        int[] f = new int[n + 1];
        for (int r = 1; r <= n; r++) {
            // 如果 [1,r] 满足回文，不需要分割
            if (g[1][r]) {
                f[r] = 0;
            } else {
                // 先设定一个最大分割次数（r 个字符最多消耗 r - 1 次分割）
                f[r] = r - 1;
                // 在所有符合 [l,r] 回文的方案中取最小值
                for (int l = 1; l <= r; l++) {
                    if (g[l][r]) f[r] = Math.min(f[r], f[l - 1] + 1);
                }
            }
        }

        return f[n];
    }
}
